package problems

import "strings"

// 804
// https://leetcode-cn.com/problems/unique-morse-code-words/
func UniqueMorseRepresentations(words []string) int {
	mos := []string{".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---", "-.-", ".-..", "--", "-.", "---", ".--.", "--.-", ".-.", "...", "-", "..-", "...-", ".--", "-..-", "-.--", "--.."}
	codes, codeStr := make(map[string]bool), ``
	for _, word := range words {
		code := make([]string, 0)
		for _, v := range word {
			code = append(code, mos[v-'a'])
		}
		codeStr = strings.Join(code, ``)
		if _, ok := codes[codeStr]; !ok {
			codes[codeStr] = true
		}
	}
	return len(codes)
}

// 806
// https://leetcode-cn.com/problems/number-of-lines-to-write-string/
func NumberOfLines(widths []int, s string) []int {
	res := []int{0, 0}
	if len(s) == 0 {
		return res
	}
	res[0] = 1
	for _, v := range s {
		res[1] += widths[v-'a']
		if res[1] > 100 {
			res[0]++
			res[1] = widths[v-'a']
		}
	}

	return res
}

// 841
// https://leetcode-cn.com/problems/keys-and-rooms/
func CanVisitAllRooms(rooms [][]int) bool {
	var currentKey int
	var keys []int
	var inRooms = make(map[int]struct{})
	var value = struct{}{}
	if len(rooms) > 0 {
		keys = rooms[0]
		inRooms[0] = value
	}
	for len(keys) > 0 {
		currentKey, keys = keys[0], keys[1:]
		if _, ok := inRooms[currentKey]; ok {
			continue
		}
		for _, v := range rooms[currentKey] {
			if _, ok := inRooms[v]; ok {
				continue
			}
			keys = append(keys, v)
		}
		inRooms[currentKey] = value
	}
	return len(inRooms) == len(rooms)
}

// 860
// https://leetcode-cn.com/problems/lemonade-change/
func LemonadeChange(bills []int) bool {
	money := [2]uint{}
	for _, v := range bills {
		switch v {
		case 20:
			if money[0] == 0 || (money[0] < 3 && money[1] == 0) {
				return false
			}
			if money[1] > 0 {
				money[0]--
				money[1]--
			} else {
				money[0] -= 3
			}
		case 10:
			if money[0] == 0 {
				return false
			}
			money[1]++
			money[0]--
		default:
			money[0]++
		}
	}
	return true
}

// 867
// https://leetcode-cn.com/problems/transpose-matrix/
func Transpose(matrix [][]int) [][]int {
	nm := make([][]int, 0)
	for j := 0; j < len(matrix[0]); j++ {
		col := make([]int, 0)
		for i := 0; i < len(matrix); i++ {
			col = append(col, matrix[i][j])
		}
		nm = append(nm, col)
	}
	return nm
}

// 868
// https://leetcode-cn.com/problems/binary-gap/
func BinaryGap(n int) int {
	max, num := 0, 0
	for n > 0 {
		if n%2 == 1 {
			if max < num {
				max = num
			}
			num = 1
		} else if num > 0 {
			num++
		}
		n /= 2
	}
	return max
}

// 872
// https://leetcode-cn.com/problems/leaf-similar-trees/
func LeafSimilar(root1 *TreeNode, root2 *TreeNode) bool {
	var order func(root *TreeNode) []int
	order = func(root *TreeNode) []int {
		var arr []int
		if root != nil {
			if root.Left == nil && root.Right == nil {
				arr = append(arr, root.Val)
			} else {
				arr = append(order(root.Left), order(root.Right)...)
			}
		}
		return arr
	}
	var arr1, arr2 = order(root1), order(root2)
	if len(arr1) != len(arr2) {
		return false
	}
	for k, v := range arr1 {
		if v != arr2[k] {
			return false
		}
	}
	return true
}

// 876
// https://leetcode-cn.com/problems/middle-of-the-linked-list/
func middleNode(head *ListNode) *ListNode {
	s, f := head, head
	for s.Next != nil && f.Next != nil {
		s, f = s.Next, f.Next
		if f.Next != nil {
			f = f.Next
		}
	}

	return s
}

// 888
// https://leetcode-cn.com/problems/fair-candy-swap/
func FairCandySwap(A []int, B []int) []int {
	numA, numB := 0, 0
	mapB := make(map[int]struct{}, len(B))
	for _, v := range A {
		numA += v
	}
	for _, v := range B {
		numB += v
		mapB[v] = struct{}{}
	}
	diff := (numB - numA) / 2
	for _, v := range A {
		if _, ok := mapB[v+diff]; ok {
			return []int{v, v + diff}
		}
	}
	return nil
}

// 896
// https://leetcode-cn.com/problems/monotonic-array/
func IsMonotonic(A []int) bool {
	res := 3
	for i := 0; i < len(A)-1; i++ {
		if A[i] < A[i+1] {
			res &= 1
		} else if A[i] > A[i+1] {
			res &= 2
		}
	}

	return res > 0
}

// 897
// https://leetcode-cn.com/problems/increasing-order-search-tree/
func IncreasingBST(root *TreeNode) *TreeNode {
	var pre, first *TreeNode
	var order func(root *TreeNode)
	order = func(root *TreeNode) {
		if root != nil {
			order(root.Left)
			if first == nil {
				first = root
			}
			if pre != nil {
				pre.Left = nil
				pre.Right = root
			}
			pre = root
			order(root.Right)
		}
	}
	order(root)
	return first
}
